乒乓游戏

Time Limit: 10 Sec Memory Limit: 256 MB

Description

img

Input

img

Output

img

Sample Input

5
　　1 1 5
　　1 5 11
　　2 1 2
　　1 2 9
　　2 1 2

Sample Output

NO
　　YES

HINT

img

Main idea

如果一个区间的端点在区间内，则这个区间可以走到那个区间，询问一个区间能否到另一个区间。

Source

首先我们立马想到了：如果两个区间严格有交集，那么这两个区间所能到达的区间集合是一样的。那么如果两个区间严格有交集的话我们就可以把它们合并起来，这里运用并查集。

这样处理完之后，剩下的区间只有两种情况：包含或者相离。那么查询的时候显然只要判断两个区间指向的大区间的情况即可。

我们要怎么合并呢？显然就是在线段树上进行操作，对于线段树上的每个节点开个vector，存下严格包含这个节点表示的[l,r]的区间的编号，那么我们加入新区间的时候，只要把左右端点在线段树上往下走，如果遇到这个线段树上的节点上的vector有东西，就记录几个区间的最小左端点以及最大右端点，把这几个区间的父亲都指向这个新区间，再删除掉这几个区间即可。然后合并完之后，把得到的新区间再放到各个点的vector进去。

最后，由于这题区间端点权比较大，所以要先离散化。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>
using namespace std;

const int ONE=100005*8;
const int INF=1e9+1;

int n;
int Num,cnt;

vector <int> Node[ONE];

struct power
{
    int l,r,opt;
}a[ONE],interval[ONE];

int Q[ONE],li_num;
struct LISAN
{
    int pos,val;
}Li[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

namespace LI
{
    void add(int i)
    {
        if(a[i].opt!=1) return;
        Num++;
        Li[++li_num].val = a[i].l;    Li[li_num].pos = li_num;
        Li[++li_num].val = a[i].r;    Li[li_num].pos = li_num;
    }

    int cmp(const LISAN &a,const LISAN &b) {return a.val < b.val;}
    void Lisan()
    {
        sort(Li+1, Li+li_num+1, cmp);

        cnt=0;
        Li[0].val=-INF;
        for(int i=1;i<=li_num;i++)
        {
            if(Li[i].val!=Li[i-1].val) ++cnt;
            Q[Li[i].pos]=cnt;
        }
        Num=cnt;

        cnt=0;
        for(int i=1;i<=n;i++)
            if(a[i].opt==1)
                a[i].l=Q[++cnt], a[i].r=Q[++cnt];

    }
}

int fat[ONE];
int Find(int x)
{
    if(fat[x]==x) return x;
    return fat[x]=Find(fat[x]);
}

namespace Seg
{
    void Delete(int i,int l,int r,int L)
    {
        if(Node[i].size())
        {
            for(int j=0; j<Node[i].size(); j++)
            {
                int id=Node[i][j];
                fat[ Find(id) ] = cnt;
                interval[cnt].l = min(interval[cnt].l, interval[id].l);
                interval[cnt].r = max(interval[cnt].r, interval[id].r);
            }
            Node[i].clear();
        }
        if(l==r) return;
        int mid = (l+r)>>1;
        if(L <= mid) Delete(i<<1, l, mid, L);
        else Delete(i<<1|1, mid+1, r, L);
    }

    void Update(int i,int l,int r,int L,int R)
    {
        if(L>R) return;
        if(L<=l && r<=R)
        {
            Node[i].push_back(cnt);
            return;
        }
        int mid=(l+r)>>1;
        if(L<=mid) Update(i<<1,l,mid,L,R);
        if(mid+1<=R) Update(i<<1|1,mid+1,r,L,R);
    }
}

bool P_edge(power a,power b)
{
    if( (b.l<a.l && a.l<b.r) || (b.l<a.r && a.r<b.r)) return 1;
    return 0;
}

int main()
{
    n=get();
    for(int i=1;i<=n;i++)
    {
        a[i].opt=get();
        a[i].l=get();    a[i].r=get();
        LI::add(i);
    }
    for(int i=1;i<=Num;i++) fat[i]=i;

    LI::Lisan();

    cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].opt==1)
        {
            interval[++cnt] = a[i];
            Seg::Delete(1,1,Num, a[i].l);
            Seg::Delete(1,1,Num, a[i].r);
            Seg::Update(1,1,Num, interval[cnt].l+1,interval[cnt].r-1);
        }
        else
        {
            int x=Find(a[i].l), y=Find(a[i].r);
            if(x==y || P_edge(interval[x] , interval[y]))
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
}